3  Group Actions

3.1 An Activity in Group Actions

Consider two people who can have one of two states, either standing or seated. We label the standing state as \(U\) (for ‘up’) and the seated state as \(D\) (for ‘down’). The instruction to ‘invert’ means to change from one of these states to the other. The instruction ‘swap’ means that the two people change places and we denote the two places as \(L\) (left) and \(R\) (right). We now define the operation \(a\) as ‘swap position then invert L’.

Example 3.1 \[DD \quad \xrightarrow{a} \quad UD \quad \xrightarrow{a} \quad UU \quad \xrightarrow{a} \quad DU \quad \xrightarrow{a} \quad DD\] Note the following: \[DD \quad \xrightarrow{a^2} \quad UU\] \[DD \quad \xrightarrow{a^3} \quad DU\] \[DD \quad \xrightarrow{a^4 = e} \quad DD\]

We can now form an operation table as follows: \[\begin{array}{c|cccc}*&e&a&a^2&a^3\\\hline e&e&a&a^2&a^3\\a&a&a^2&a^3&e\\a^2&a^2&a^3&e&a\\a^3&a^3&e&a&a^2\end{array}\]

So, as is easily discernible from the table, the transformations \(\{e, a, a^2, a^3\}\) form a group and as \(a\) has order 4 this group is isomorphic to \(\Z_4\).

Using the same terminology as the previous example, consider now three people seated and let \(L\) be the instruction that the two people on the left invert and \(R\) be that the two people on the right invert (so, in each case, the middle person inverts). We have the following: \[DDD \quad \xrightarrow{L} \quad UUD \quad \xrightarrow{L} \quad DDD\] So, \(L^2 = e\) and, similarly, \(R^2 = e\). We further have \[DDD \quad \xrightarrow{L} \quad UUD \quad \xrightarrow{R} \quad UDU\] and \[DDD \quad \xrightarrow{R} \quad DUU \quad \xrightarrow{L} \quad UDU.\] Hence, \(LR=RL\). Since we have that \(LR=RL\), the only distinct elements are \(e, L, R\), and \(LR\). We can then construct the operation table: \[\begin{array}{c|cccc}*&e&L&R&LR\\\hline e&e&L&R&LR\\L&L&e&LR&R\\R&R&LR&e&L\\LR&LR&R&L&e\end{array}\]

For example, \(R*LR = R(LR)=R(RL)=R^2L=L\) as \(R^2=e\). In this case, we can see from the table that all of the non-identity elements have order 2 (the identity element appears in every position on the lead diagonal) and so this group is isomorphic to \(\Z_2 \times \Z_2\). As a presentation, this group is \[\langle L, R \where L^2=R^2=e, LR=RL\rangle.\]

Example 3.2 Consider three people seated. Let \(a\) : invert \(L\), swap the other two; \(b\) : invert \(R\), swap the other two. Find the distinct elements of the group and construct the operation table. What is this group?

Observe that \(a\) and \(b\) both have order two. Moreover \((ab)^3 = 1\):

\[ D_{L}DD_{R} \quad \xrightarrow{ab} \quad D_{R}U_{L}U \quad \xrightarrow{ab} \quad UU_{R}D_{L} \quad \xrightarrow{ab} \quad D_{L}DD_{R}. \]

Thus the group generated by \(a\) and \(b\) has the same presentation as the group in Example 1.9 and so is isomorphic to \(D_3\).

3.2 Groups Acting on Sets

We have already seen several examples of groups acting on sets but have not introduced the concept formally. Each element of \(D_3\) permutes the vertices of the triangle and we say that the group ‘acts’ on these vertices.

Consider rotation anticlockwise by \(\pi/3\)

Then \(r_1\) ‘acts’ on vertex \(1\) by mapping it to position \(2\) and so on. We can represent this action on the set \(\{1,2,3\}\) of vertices as: \[ \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} = (1 \; 2 \; 3). \]

A group \(G\) acts on a set \(X\) when each element of \(G\) maps each element of \(X\) onto another element of \(X\) in a way consistent with the group axioms. Formally we have:

Definition 3.1 (Group Action) A group \(G\) acts on a (non-empty) set \(X\) (or there is an action \(*\) of \(G\) on \(X\)) if, for each \(g\in G\) and \(x\in X\) there is an element \(g*x\in X\) and

1. \(e*x=x, \; \forall \, x\in X\),
2. \(g*(h*x)=(gh)*x, \; \forall \, g,h\in G\) and \(\forall \, x\in X\).

The first property requires that the effect of the identity element in \(G\) is the identity permutation on \(X\) and the second says that the effect of applying \(h\) followed by \(g\) to an element of \(X\) is the same as applying the single element \(gh\). Groups acting on sets are really just thinly disguised permutation groups in that whenever a group \(G\) acts on a set \(X\) we can associate with each \(g\in G\) the permutation \(f_g\) of \(X\) defined by \(f_g(x)=g*x,\ \forall \, x\in X\). These permutations form a subgroup of \(S_{|X|}\), but this group need not be isomorphic to \(G\), and we shall return to this later. First we consider some examples.

Example 3.3  

Consider the symmetric group \(S_n\). This acts on the set \(\{1,2,\ldots, n\}\) by the rule \(f \ast x = f(x)\). For example, for \(f = (1 \; 2 \; 4)\), then \[\begin{align*} f\ast 1 &= 2\\ f \ast 3 &= 3. \end{align*}\]

Notice that this extends to any subgroup of \(S_n\), that is any subgroup \(H \le S_n\) acts on the set \(\{1,2, \ldots, n\}\) in the manner just described. By Cayley’s Theorem, this means that every finite group acts on a finite set (recall that in Cayley’s theorem this set is just the group elements and so every group acts on itself).

Example 3.4  

Consider the group \(D_4\). This group acts on the set \(N = \{1,2,\ldots, 9\}\) of nine small squares in a 3x3 array as follows:

\[ \begin{array}{|c|c|c|} \hline 1&2&3\\ \hline 4&5&6\\ \hline 7&8&9\\ \hline \end{array} \]

Using our notation for the symmetries of a square we have, for example,

\[\begin{align*} r_1 \ast 7 &= 9 \\ r_2 \ast 5 &= 5 \\ s_1 \ast 3 &= 1 \end{align*}\]

Example 3.5  

Let \(V= \{1,2,3,4\}\) be the set of numbered vertices of a square as shown with symmetries defined as usual.

If we let \(D_4\) acts on the vertices of the square, then we are led to the permutation group: \[ \begin{array}{cccc} \stackrel{\begin{pmatrix}1 & 2 & 3 & 4\\ 1 & 2 & 3 & 4 \end{pmatrix},}{e} & \stackrel{\begin{pmatrix}1 & 2 & 3 & 4\\ 2 & 3 & 4 & 1 \end{pmatrix},}{r_1} & \stackrel{\begin{pmatrix}1 & 2 & 3 & 4\\ 3 & 4 & 1 & 2 \end{pmatrix},}{r_2} & \stackrel{\begin{pmatrix}1 & 2 & 3 & 4\\ 4 & 1 & 2 & 3 \end{pmatrix},}{r_3} \\ \stackrel{\begin{pmatrix}1 & 2 & 3 & 4\\ 2 & 1 & 4 & 3 \end{pmatrix},}{s_1} & \stackrel{\begin{pmatrix}1 & 2 & 3 & 4\\ 1 & 4 & 3 & 2 \end{pmatrix},}{s_2} & \stackrel{\begin{pmatrix}1 & 2 & 3 & 4\\ 4 & 3 & 2 & 1 \end{pmatrix},}{s_3} & \stackrel{\begin{pmatrix}1 & 2 & 3 & 4\\ 3 & 2 & 1 & 4 \end{pmatrix}.}{s_4} \end{array} \] This permutation group is isomorphic to \(D_4\).

The group \(D_4\) can also act on the diagonals of the square (so ignoring vertices and thinking only of how the diagonals are affected). Writing \(d_1\) for the main diagonal and \(d_2\) for the off diagonal, we see that \(e, r_2, s_2, s_4\) all fix the diagonals while all other elements of \(D_4\) swap the diagonals. We can represent this action by the permutation group: \[ \left\{ \begin{pmatrix} d_1 & d_2 \\ d_1 & d_2 \end{pmatrix}, \begin{pmatrix} d_1 & d_2 \\ d_2 & d_1 \end{pmatrix} \right\}. \]

Example 3.6  

Consider the group \(\glr{n}\), the group of invertible \(n\times n\) matrices with real entries under matrix multiplication. This acts on the \(\R^{n}\) by \(A \ast \vecx = A \vecx\) since: \[I \ast \vecx = I \vecx = \vec x\] and \[B \ast (A \ast \vec x) = B \ast (A \vecx) = BA \vecx = (BA) \ast \vecx.\]

Any group of functions \(G\) on a set \(X\) defines a group action \(*\) according to the ‘obvious’ rule \(f*x=f(x), \forall \, x\in X\). By definition of the identity function, \(e\), we have \(e*x=x, \forall \, x\in X\) and, since \(g*(f*x)\) means apply \(g\) to \(f(x)\), it follows immediately that \(\forall \, g,f \in G, \, g*(f*x)=(gf)*x\) as they are both just \(g(f(x))\). However, many deep theorems of Group Theory have been proved by finding a ‘good action’. A good example is the following alternative proof to one of the main results on permutations in the Abstract Algebra module. We give an example first, followed by the proof.

Theorem 3.1 No permutation can be expressed both as a product of an even number of transpositions and as a product of an odd number of transpositions.

Example 3.7 Let \(S_4\) act on the set of polynomials in \(\{x_1, x_2, x_3, x_4\}\) by the rule \(f:x_i \maps x_{f(i)}\). For example, \[(1 \; 2)(3 \; 4) * (x_1^3x_2-x_3) = x_2^3x_1-x_4.\] Now consider the polynomial \[P=\prod_{1 \leq i<j\leq 4}(x_j-x_i)= (x_2-x_1)(x_3-x_2)(x_3-x_1)(x_4-x_3)(x_4-x_2)(x_4-x_1).\] Then \[(1 \; 2)P = (x_1-x_2)(x_3-x_1)(x_3-x_2)(x_4-x_3)(x_4-x_1)(x_4-x_2) = -P\] since the only overall change is \((x_2-x_1) \mapsto (x_1-x_2) = -(x_2-x_1).\) Also \[(1 \; 3)P = (x_2-x_3)(x_1-x_2)(x_1-x_3)(x_4-x_1)(x_4-x_2)(x_4-x_3) = -P\] since the first three terms change parity. In fact we have that, for all \((i \; j) \in S_4, \;\; (i \; j)*P = -P\).

We can now prove the theorem.

Proof. Let \(S_n\) act on the set of polynomials \(\{x_1, x_2, \ldots, x_n\}\) by the rule \(f:x_i \mapsto x_{f(i)}\). Consider the so-called alternating polynomial \[P = \prod_{1 \leq i < j \leq n} (x_j - x_i).\] For all transpositions \((i \; j) \in S_n\), then \((i \; j)*P = -P\). If \(f\) can be written as the product of an even number of transpositions, then \(f*P=P\). If \(f\) can be written as the product of an odd number of transpositions, then \(f*P=-P\). Hence, \(f\) cannot be expressed as the product of both an even number and an odd number of transpositions.

3.3 Orbits and Stabilizers

Let \(G\) be a group acting on a set \(X\). Given \(x\in X\) we define the orbit of \(x\), \(\orb (x)\) to be the set of elements of \(X\) that we can obtain from \(x\) by applying some element of \(G\). Formally we have:

Definition 3.2 (Orbit) Let \(G\) be a group acting on a set \(X\). Then the orbit of \(x\) is denoted and defined by \[\orb (x)=\{y\in X \, | \, y=g*x\mbox{ for some }g\in G\}.\]

Example 3.8  

We apply Definition 3.2 to some groups we have encountered already.

• The orbits of the cyclic subgroup of \(S_n\) generated by an element \(f \in S_n\) are the cycles of \(f\) written as sets. For example the orbit of the group \(\gen{(1 \; 2) (3 \; 4 \; 5 \; 7)} \le S_{7}\) are \(\{1,2\}, \{3,4,5,7\}, \{6\}\).

• Consider Example 3.5: \(D_4\) acting on the vertices has only one orbit: \(\{1,2,3,4\}\). However in Example 3.4, the orbits of \(D_4\) are \(\{1,3,7,9\}, \{2,4,6,8\}, \{5\}\).

It would appear that the orbits partition \(X\) and the standard way to prove the existence of a partition is to show that there is an underlying equivalence relation.

Lemma 3.1 Let \(G\) be a group acting on a set \(X\). Define the relation \(\sim\) on \(X\) by \(x\sim y\) if and only if \(g*x=y\) for some \(g\in G\) (i.e. \(x\) is related to \(y\) if and only if \(y\) is in the orbit of \(x\)). Then \(\sim\) is an equivalence relation on \(X\).

Proof.

We verify that the relation is reflexive, symmetric and transitive.

• Reflexive: for all \(x \in X\), \(e \ast x = x\), therefore \(x \in \orb(x)\) and \(x \sim x\).
• Symmetric: \(x \sim y \implies g \ast x = y\) for some \(g \in G\). However this now means that \[x = e \ast x = (g^{-1} g) \ast x = g^{-1} \ast (g \ast x) = g^{-1} \ast y\] and so \(y \sim x\).
• Transitive: \(x \sim y\) and \(y \sim z\). There are \(g_1, g_2\) such that \(g_1 \ast x = y\) and \(g_2 \ast y = z\). This now means that \[(g_2 g_1) \ast x = g_2 \ast(g_1 \ast x) = g_2 \ast y = z\] and so \(x \sim z\).

The stabilizer of \(x\), \(\stab (x)\), consists of those elements of \(G\) that leave \(x\) unchanged. Formally we have:

Definition 3.3 (Stabilizer) Let \(G\) be a group acting on a set \(X\). Then the stabilizer of \(x \in X\) is denoted and defined by \[\stab (x)=\{g\in G \, | \, g*x = x\}.\]

Example 3.9  

Consider Example 3.4 and Example 3.5:

• In Example 3.4: \(\stab(2) = \{e,s_1\}\), \(\stab(5) = D_4\)
• In Example 3.5: \[\begin{align*} \stab(1) &= \{e,s_2\} = \stab(3)\\ \stab(2) &= \{e,s_4\} = \stab(4)\\ \stab(d_1) &= \{e,r_2,s_2,s_4\} = \stab(d_2) \end{align*}\]

Note

For a group \(G\) acting on a set \(X\), the orbits are subsets of \(X\) whereas the stabilizers are subsets of \(G\). In fact a stabilizer is rather more than just a subset of \(G\)!

Theorem 3.2 Let \(G\) be a group acting on a set \(X\). Then \(\stab (x)\) is a subgroup of \(G\).

Proof.

Note that \(e \in \stab(x)\) since \(e \ast x = x\).

Let \(g, h \in \stab(x)\), then \[(gh)\ast x = g \ast (h \ast x) = g \ast x = x\] and so \(gh \in \stab(x)\). Furthermore, \[ x = e \ast x = (g^{-1} g) \ast x = g^{-1} \ast (g \ast x) = g^{-1} \ast x\] and so \(g^{-1} \in \stab(x)\).

This completes the subgroup check.

Example 3.10  

Consider Example 3.4 and Example 3.5 again:

• Revisiting Example 3.4: \[ \begin{array}{c|c} \text{Orbit} & \text{stabilizer}\\ \hline \orb(1) = \{1,3,7,9\} & \stab(1) = \{e, s_4\} \\ \orb(2) = \{2,4,6,8\} & \stab(2) = \{e, s_1\} \\ \orb(5) = \{5\} & \stab(5) = D_4 \end{array} \]
• Revisiting Example 3.5: \[ \begin{array}{c|c} \text{Orbit} & \text{stabilizer}\\ \hline \orb(1) = \{1,2,3,4\} & \stab(1) = \{e, s_2\} \\ \orb(d_1) = \{d_1,d_2\} & \stab(d_1) = \{e, r_2, s_2, s_4\} \end{array} \]

Notice that in each of the cases above: \[|\orb(x)| \times |\stab(x)| = |D_4|.\] This fact holds in general.

Theorem 3.3 (Orbit Stabilizer Theorem) Let \(G\) be a finite group acting on a finite set \(X\), and \(x\in X\). Then: \[|\orb(x)| \times |\stab(x)| = |G|.\]

Proof.

Recalling, by Lagrange’s theorem, that the index of \(\stab(x)\) in \(G\) is precisely \(|G|/|\stab(x)|\), it suffices to show that orbit \(x\) is in one-to-one correspondence with the left cosets of \(\stab(x)\) in \(G\). We do this by showing that \(g_1 \ast x = g_2 \ast y\), for \(g_1, g_2 \in G\) if and only if \(g_1\) and \(g_2\) belong to the same left coset.

Suppose first that \(g_1\) and \(g_2\) belong to the same left coset of \(\stab(x)\). This means that there is an \(h \in \stab (x)\) such that \(g_1 h = g_2\). Consequently: \[ g_2 \ast x = (g_1 h) \ast x = g_1 \ast (h \ast x) = g_1 \ast x\] as required.

Suppose on the other hand that \(g_1 \ast x = g_2 \ast x\). We then have: \[ x = e \ast x = (g_1^{-1}g_1) \ast x = g_{1}^{-1}\ast(g_1 \ast x) = g_{1}^{-1}\ast(g_2 \ast x) = (g_{1}^{-1} g_2) \ast x)\] and we conclude that \(g_1^{-1}g_2 \in \stab(x)\). Therefore, \(g_1\) and \(g_2\) belong to the same left coset of \(\stab(x)\).

Later we will use this result to prove an important structural property of groups, namely Cauchy’s Theorem which states that if \(p\) is a prime divisor of the order of a group \(G\), then \(G\) contains an element (and hence a subgroup) of order \(p\). This is the first step towards a ‘converse’ to Lagrange’s Theorem. Before we do this, though, we prove a famous result that has many important applications.

3.4 Counting Orbits

Let \(G\) be a group acting on a set \(X\). For each \(g\in G\), the fixed set of \(g\), \(\fix (g)\), is the subset of \(X\) consisting of those elements of \(X\) fixed by \(g\). Formally we have:

Definition 3.4 (Fixed Set) Let \(G\) be a group acting on a set \(X\). Then, for each \(g \in G\), the fixed set of \(g\) is denoted and defined by \[\fix (g)=\{x\in X \, | \, g*x=x\}.\]

Example 3.11  

Consider Example 3.4 with \(D_4\) acting on the four vertices of a square. We have: \[\begin{align*} \fix(e) &= \{1,2,3,4\} \\ \fix(r_1) &= \fix(r_2) = \fix(r_3) = \emptyset \\ \fix(s_1) &= \fix(s_3) = \emptyset \\ \fix(s_2) &= \{1,3 \} \\ \fix(s_4) &= \{2,4 \}. \end{align*}\] Notice that \[ \sum_{g \in D_4} |\fix(g)| = 8 \] and \[ \sum_{x \in V} |\stab(x)| = 8 \] For this example we have \(\sum_{g \in G} |\fix(g)|=\sum_{x \in V} |\stab(x)|\).

We prove that this holds in general. The key idea is to consider the set of all pairs \((g,x)\) such that \(g\ast x = x\). We can order this set of pairs in two ways: \[ \{ (g,x) \mid x \in \fix(g) \} = \{(g,x) : g \in \stab(x)\}.\] For instance, returning to Example 3.4 again, we have, under the first ordering, \[ \{(e,1),(e,2),(e,3),(e,4),(s_2,1),(s_2,3),(s_4,2),(s_4,4)\} \] and under the second, \[ \{(e,1),(s_2,1),(e,2),(s_4,2),(e,3)(s_2,3),(e,4),(s_4,4)\}. \] As expected the two sets are equal and consequently: \[\sum_{g \in D_4}|\fix(g)| = \sum_{x \in V} |\stab(x)|\] since both sums count the number of pairs \((g,x)\) such that \(g \ast x = x\).

Notice that \(\fix (g)\) is a subset of \(X\) (as is \(\orb (x)\) but not \(\stab (x)\) which is a subgroup of \(G\)). However, \(\fix (g)\) and \(\stab (x)\) are related.

Lemma 3.2 Let \(G\) be a finite group acting on a finite set \(X\), then \[\sum_{g\in G}|\fix (g)| = \sum_{x\in X}|\stab (x)|.\]

Proof.

Let \(N\) be the size of the set \[\{(g, x): g \in G, x \in X, g \ast x = x\}.\] Then, \[ N = |\{(g, x): g \in G, x \in X, g \ast x = x\}| = \sum_{g \in G} |\{(g,x) : x \in \fix(g)\}| = \sum_{g \in G} |\fix(g)|\] and \[ N = |\{(g, x): g \in G, x \in X, g \ast x = x\}| = \sum_{x \in X} |\{(g,x) : g \in \stab(x)\}| = \sum_{x \in X} |\stab(x)|.\] The result now follows.

We are now in a position to prove Burnside’s Lemma, which should really be called a Theorem (but then it wasn’t proved by Burnside either).

Theorem 3.4 (Burnside’s Lemma) Let \(G\) be a finite group acting on a finite set \(X\). Then \[\mbox{the number of orbits in $X$ under $G$ }=\frac{1}{|G|}\sum_{g\in G}|\fix (g)|.\]

Proof.

Let \(O_1, O_2, \ldots, O_r\) be the \(r\) orbits of \(X\) under \(G\) and consider the \[ \sum_{x \in X} | \stab(x)|.\] Recalling that the orbits of \(X\) form a partition of \(X\), we can organise the above sum as: \[ \sum_{x \in X} | \stab(x)| = \sum_{x \in O_1} | \stab(x)| + \sum_{x \in O_2} | \stab(x)| + \ldots + \sum_{x \in O_r} | \stab(x)|. \] We next observe that points in the same orbit have stabilizers of equal sizes. This is a consequence of Theorem 3.3 since for \(x,y\) belonging to the same orbit \(O\): \[ |\stab(x)| = \frac{|G|}{|O|} = |\stab(y)|. \] Therefore fixing, for each \(1 \le i \le r\) a point \(x_i \in O_r\), \[\begin{align*} \sum_{x \in X} | \stab(x)| &= \sum_{x \in O_1} | \stab(x)| + \sum_{x \in O_2} | \stab(x)| + \ldots + \sum_{x \in O_r} | \stab(x)| \\ &= (|O_1| \times |\stab(x_1)|) + (|O_2| \times |\stab(x_2)|) + \ldots + (|O_r| \times |\stab(x_r)|) \\ &= |G| r \end{align*}\] Dividing by \(|G|\) yields, \[ \frac{1}{|G|} \sum_{x \in X} | \stab(x)| = r. \] The result is now a consequence of Lemma 3.2.

3.5 Colouring Problems

Burnside’s lemma can be used to count the number of ‘essentially different’ configurations in a set. As in Graph Theory, these configurations are usually described in terms of colourings but the applications are much wider than this suggests.

Example 3.12 How many essentially different ways are there of colouring the smaller equilateral triangles red, blue or yellow?

The answer depends on what is meant by ‘essentially’ different.

We may wish to consider \(1\) and \(2\) the same since we may obtain \(2\) from \(1\) by applying the symmetry \(r_2\) in \(D_3\) (rotating anticlockwise twice by \(2\pi/3\)).

If the triangle is equilateral, then we may consider all the labellings to be equivalent, since we may obtain \(3\) from \(1\) by reflecting in the vertical axis (that is by applying the element \(s_2\) of \(D_3\)).

To be precise about what we mean by ‘essentially different’ we specify a group of symmetries of the figure and say that two colourings are equivalent (i.e. essentially the same) if and only if one can be transformed into the other by one of these symmetries. In other words, if we consider the action of a group of symmetries on the set of all colourings of the figure, then two colourings are equivalent if and only if they lie in the same orbit. It follows that the number of distinct colourings is just the total number of orbits, which we can find using Burnside’s Lemma.

Example 3.13 In how many different ways can the square glass tile shown below, which can be turned over, be coloured

1. using \(n\) colours,
2. so that there are six red and two blue regions?

The group acting is \(D_4\):

1. The underlying set \(X\) is the set of all \(n^{8}\) colourings of the \(8\) regions of the tile. Hence \(|\fix(e)| = |X| = n^8\).

   

   By Burnside’s Lemma, the number of orbits of \(X\) under \(D_4\), that is the total number of distinct colourings, is \[\frac{1}{8} (n^8 + 5n^4 + 2n^2).\]

2. There are \(\binom{8}{2}\) ways of choosing the blue colored regions; the rest are colored red. Therefore the total number of colorings is \[\binom{8}{2} = 28.\] This means that \(\fix(e) = 28\). Looking at the working for part a., a colouring of the tile with blue and red that is fixed by \(r_1\) or \(r_3\) is either monochromatic or has at least \(4\) blue regions. Therefore \(\fix(r_1) = \fix(r_3) = \emptyset\) since there are no colourings of the tile with \(6\) red and \(2\) blue regions fixed under \(r_1\) or \(r_3\).

   Looking at the working for \(r_2\) we need at that exactly one of \(A,B,C,D\) is blue (the rest are red). Thus there are \(4\) such colourings. A similar argument works for the reflections – each fixes \(4\) colourings.

   Hence the number of valid colourings is: \[\frac{1}{8}(28 + (5 \times 4)) = 6.\]

3.6 Cauchy’s Theorem and \(p\)-Groups

Up to now this chapter has been concerned with applications of (permutation) groups. The main aim of this course, however, is to examine the structure of finite groups. Lagrange’s Theorem is a structure theorem in that for any finite group \(G\) it rules out the existence of subgroups of \(G\) for any order not dividing \(|G|\). We know that the converse of Lagrange’s Theorem is true for abelian groups but false in general. This is not the end of the story, as we shall eventually show that if \(|G|=p^rm\) for some prime \(p\), then \(G\) has a subgroup of order \(p^r\) (and in fact of order \(p^s\ \forall \, s,\ 0\leq s\leq r\)). Our first step towards this goal is to prove that if \(p\) is a prime divisor of the order of a group \(G\), then \(G\) contains an element of order \(p\). We will illustrate the proof of this result by way of an example.

Example 3.14 Consider \(D_3=\{e,r_1,r_2,s_1,s_2,s_3\}\), we will use group actions to show that at least one of these elements has order \(3\). Form the set \(X\) consisting of all triples \((x,y,z)\) where \(x,y\) and \(z\) are (not necessarily distinct) elements of \(G\) such that \(xyz=e\). Thus: \[\begin{align*} X = \{&(e,e,e),(e,r_1,r_2),(e,r_2,r_1),(r_1,e,r_2),(r_1,r_2,e),(r_2,e,r_1), \\&(r_2,r_1,e),(e,s_1,s_1),(s_1,e,s_1),(s_1,s_1,e),(e,s_2,s_2),(s_2,e,s_2),\\ &(s_2,s_2,e),(e,s_3,s_3),(s_3,e,s_3),(s_3,s_3,e),(r_1,r_1,r_1),(r_1,s_1,s_3),\\ &(s_3,r_1,s_1),(s_1,s_3,r_1),(r_1,s_2,s_1),(s_1,r_1,s_2),(s_2,s_1,r_1),(r_1,s_3,s_2),\\ &(s_2,r_1,s_3),(s_3,s_2,r_1),(r_2,r_2,r_2),(r_2,s_1,s_2),(s_2,r_2,s_1),(s_1,s_2,r_2),\\ &(r_2,s_2,s_3),(s_3,r_2,s_2),(s_2,,s_3,r_2),(r_2,s_3,s_1),(s_1,r_2,s_3),(s_3,s_1,r_2)\}. \end{align*}\] We see that \(|X|=36\). We should have expected this because for any choice of elements \(x\) and \(y\), \((x,y,z)\in X\) if and only if \(z=(xy)^{-1}\); there are 6 choices for \(x\) and 6 for \(y\) giving \(6\times 6=36\) triples in total. We now consider the action of the cyclic group \(\langle(1\ 2\ 3)\rangle\) on \(X\) defined by \((1\ 2\ 3)*(x,y,z)=(z,x,y)\). First we need to show that this is a group action on \(X\), so we need to show that if \((x,y,z)\in X\), then \((z,x,y)\in X\) and \((y,z,x)\in X\). But \(xyz=e \Leftrightarrow z=(xy)^{-1}\), so \(zxy=(xy)^{-1}xy=e\) and \(yzx=y(xy)^{-1}x=yy^{-1}x^{-1}x=e\) as required. What are the orbits of this action on \(X\)? \[\begin{align*} &\{(e,e,e)\}\\ &\{(e,r_1,r_2),(r_2,e,r_1),(r_1,r_2,e)\}\\ &\{(e,r_2,r_1),(r_1,e,r_2),(r_2,r_1,e)\}\\ &\{(e,s_1,s_1),(s_1,e,s_1),(s_1,s_1,e)\}\\ &\{(e,s_2,s_2),(s_2,e,s_2),(s_2,s_2,e)\}\\ &\{(e,s_3,s_3),(s_3,e,s_3),(s_3,s_3,e)\}\\ &\{(r_1,r_1,r_1)\}\\ &\{(r_1,s_1,s_3),(s_3,r_1,s_1),(s_1,s_3,r_1)\}\\ &\{(r_1,s_2,s_1),(s_1,r_1,s_2),(s_2,s_1,r_1)\}\\ &\{(r_1,s_3,s_2),(s_2,r_1,s_3),(s_3,s_2,r_1)\}\\ &\{(r_2,r_2,r_2)\}\\ &\{(r_2,s_1,s_2),(s_2,r_2,s_1),(s_1,s_2,r_2)\}\\ &\{(r_2,s_2,s_3),(s_3,r_2,s_2),(s_2,s_3,r_2)\}\\ &\{(r_2,s_3,s_1),(s_1,r_2,s_3),(s_3,s_1,r_2)\} \end{align*}\]

We see that the orbits are all either of size 1 or of size 3, moreover the orbits of size 1 are of the form \(\{(g,g,g)\}\) where \(g\) is either the identity or an element of order 3. Could we have anticipated this? Under the action described any orbit of size 1 is necessarily of the form \(\{(g,g,g)\}\) and hence \(g^3=e\); clearly \(\{(e,e,e)\}\) will give us one such orbit and any further orbits of size 1 will correspond to elements of order 3. So \(D_3\) contains an element of order 3 if and only if \(\{(e,e,e)\}\) is not the only orbit of size 1 in \(X\) under this action. Let there be \(s\) orbits of size 1 and \(t\) orbits of size \(3\), so \(|X|=s+3t\), but we know that \(|X|=36\), so \(s=36-3t=3(12-t)\). It follows that \(s\) is at least 1 and also a multiple of 3, so there are at least 3 orbits of size 1 with at least 2 corresponding to elements of order 3.

Theorem 3.5 (Cauchy’s Theorem) Let \(G\) be a finite group of order \(n\) and let \(p\) be a prime divisor of \(n\). Then \(G\) has an element of order \(p\) and, consequently, a subgroup of order \(p\).

Proof. The proof that follows is non-examinable.

Let \(n=mp\) and \(X = \{(g_1, g_2, \ldots, g_p) \in G \times G \times \ldots \times G \where g_1g_2\ldots g_p = e \}\).

Note that \(|X|=n^{p-1}\) since, for any choice of \(g_1, g_2, \ldots, g_{p-1}\) in \(G\) (and there are \(n\) choices for each of the \(g_i\) in the list), we set \(g_p = (g_1g_2\ldots g_{p-1})^{-1}.\) But \(|X|=n^{p-1} = (pm)^{p-1}\) so \(p\) divides \(|X|\). Consider the group action of \(\langle (1 \; 2 \; \ldots \; p) \rangle\) on \(X\) defined by \[(1 \; 2 \; \ldots \; p) * (g_1, g_2, \ldots, g_p) = (g_2, \ldots, g_p, g_1).\] For this to be an action on \(X\) we need to show that \[(1 \; 2 \; \ldots \; p)^r * (g_1, g_2, \ldots, g_p) = (g_{r+1}, \ldots, g_p, g_1, \ldots, g_r) \in X.\] But \(g_{r+1} \ldots g_{p-1} g_p g_1 \ldots g_r = g_{r+1} \ldots g_{p-1} (g_{p-1}^{-1} \ldots g_{r+1}^{-1} g_r^{-1} \ldots g_2^{-1}g_1^{-1})g_1 \ldots g_r = e \in X\), as required.

Next consider the orbits of \(X\) under this action. We know that the size of each orbit divides the order of \(\langle (1 \; 2 \; \ldots \; p) \rangle\), which is \(p\). Therefore, each orbit has size 1 or \(p\). But an orbit has size 1 if and only if it is of the form \(\{(g, g, \ldots, g) \}\) and hence \(g^p = e\), so either \(g = e\) or \(g\) is an element of order \(p\).

Since \(|X|\) is a multiple of \(p\) and \(|X|\) is the sum of the sizes of the orbits, we have that the number of orbits of size 1 is also a multiple of \(p\) (possible zero), but \(\{ e, e, \ldots, e \}\) is one such orbit, so there must be at least \(p-1\) further orbits of size 1, and each of these is of the form \(\{(g, g, \ldots, g) \}\) where \(g \neq e\) is an element of order \(p\).

We now introduce an important class of groups.

Definition 3.5 (\(p\)-groups and \(p\)-subgroups) A group is called a p-group if and only if every element in \(G\) has order a power of the prime \(p\). A subgroup of a group \(G\) is a p-subgroup of \(G\) if the subgroup is itself a \(p\)-group.

It is not immediately obvious that finite \(p\)-groups are exactly the groups of order \(p^n\).

Theorem 3.6 Let \(G\) be a finite group. Then \(G\) is a \(p\)-group if and only if \(|G|\) is a power of \(p\).

Proof.

If \(|G|\) is a power of \(p\), then by Lagrange’s Theorem, the order of every element of \(|G|\) is also a power of \(p\) (since it has to divide the order of \(|G|\)).

Suppose \(G\) is a \(p\)-group. If \(q\) is a prime dividing \(|G|\), then by Cauchy’s Theorem (Theorem 3.5), there is an element of \(G\) of order \(q\). This means that the only prime dividing \(G\) must be \(q\) and so the order of \(G\) must be a power of \(p\).

3.7 Problem Sheet 3

For Week 7; covers Chapter 3. At minimum you should attempt questions 3.1, 3.4 and 3.5.

---

Question 3.1

Consider the group \(D_6\) (the group of symmetries of a regular hexagon) acting on the set, \(X\), of vertices of the regular hexagon shown below and numbered sequentially 1 to 6 in an anticlockwise direction with the upper left vertex being number 1.

Using our standard notation for the elements of \(D_6\):

1. find the orbits of \(X\);
2. find the stabiliser of each element of \(X\);
3. show how your results in parts a. and b. above demonstrate the Orbit-Stabiliser Theorem.

Solution 3.1

1. \(\text{orb}(1) = \{1, 2, 3, 4, 5, 6\} = \text{orb}(2) = \text{orb}(3) = \text{orb}(4) = \text{orb}(5) = \text{orb}(6)\), so there is just the one orbit of \(X\).
2. \[\begin{align*} \text{stab}(1) &= \{e, s_6\} = \text{stab}(4)\\ \text{stab}(2) &= \{e, s_4\} = \text{stab}(5)\\ \text{stab}(3) &= \{e, s_2\} = \text{stab}(6). \end{align*}\]
3. Consider \(g \in X\). Then \(|\text{orb}(g)| \times |\text{stab}(g)| = 6 \times 2 = 12 = |D_4|\). This is true for all \(g \in X\).

Question 3.2

In how many ways can the edges of a regular octagon be coloured with four different colours if two colourings are indistinguishable when one can be obtained from the other by

1. a rotation of the octagon.
2. a rotation or reflection of the octagon.

Solution 3.2

1. Here we are considering the action of the subgroup of \(D_8\) that consists of the identity and the seven rotations, That is \(G = \{e, r_1, r_2, r_3, r_4, r_5, r_6, r_7, \}\). There are four colour choices for each of the eight edges. This gives \[|X| = 4^8 = 65,536 = |\, \text{fix}(e) \, |.\] It is important to remember, in what follows, that when we label an edge with a letter, we are not referring directly to a particular colour; the letterings relate to the relationships between edges and their respective colours. So, for a given letter we have a free choice of colour, but having made that choice then that colour must be used wherever that letter appears. In general, for a regular \(n\)-gon, the rotations will be of \(\frac{i2\pi}{n}\) radians where \(i\) is an integer such that \(0 \leq i < n\). Now, for the colourings to be indistinguishable under the rotations where \(i\) and \(n\) are relatively prime (that is, in this case, odd \(i\) since \(n\) is 8) all of the edges must have the same colour. So we have that \[|\, \text{fix}(r_1) \, | = |\, \text{fix}(r_3) \, | = |\, \text{fix}(r_5) \, | = |\, \text{fix}(r_7) \, | = 4. \] For the rotations of \(\frac{\pi}{2}\) and \(\frac{3\pi}{2}\) radians, that is \(r_2\) and \(r_6\), we can have the following configuration:

   

   This, in terms of colours, means that we either use just two colours, in which case they must alternate around the edges, or just the same colour for each edge. So, we have \[|\, \text{fix}(r_2) \, | = |\, \text{fix}(r_6) \, | = 4^2 = 16. \]

   The remaining rotation, that is \(r_4\) through \(\pi\) radians, requires the following configuration:

   

   So, we have \[|\, \text{fix}(r_4) \, | = 4^4 = 256. \] Then, by Burnside’s Lemma, the number of orbits (and, hence, the number of distinct colourings) is \[\frac{1}{|G|} \sum \, |\, \text{fix}(g) \, | = \frac{1}{8} \, ( 4^8 + (4 \times 4) + (2 \times 4^2) + 4^4 ) = 8230.\]

2. Here we are considering the action of the full dihedral group \(D_8\) and so as well as the rotations discussed above we also need to look at the reflections. Note that there are two types of lines of symmetry; vertex to opposite vertex and midpoint of edge to midpoint of opposite edge. For vertex to vertex we have the following:

   

   So \[|\, \text{fix}(s_1) \, | = |\, \text{fix}(s_3) \, | = |\, \text{fix}(s_5) \, | = |\, \text{fix}(s_7) \, | = 4^4 = 256. \]

   For midpoint to midpoint we have:

   

   So \[|\, \text{fix}(s_2) \, | = |\, \text{fix}(s_4) \, | = |\, \text{fix}(s_6) \, | = |\, \text{fix}(s_8) \, | = 4^5 = 1024. \] It is important to note, in this last case, that using five letters does not imply that we need five colours! Then, by Burnside’s Lemma, the number of orbits (and, hence, the number of distinct colourings) is \[\frac{1}{|G|} \sum \, |\, \text{fix}(g) \, | = \frac{1}{16} \, ( 4^8 + (4 \times 4) + (2 \times 4^2) + 4^4 + (4 \times 4^4) + (4 \times 4^5)) = 4435.\]

Question 3.3

Use Burnside’s Lemma to count the distinguishable colourings of the edges of

1. a square,
2. a regular pentagon,

using at most three colours under the relevant full dihedral group of symmetries in each case.

Solution 3.3

1. The square: Here we are considering the action of the dihedral group \(D_4\) that consists of the identity, three rotations and four reflections. We will use the usual notation with \(r_i\) being an anticlockwise rotation through \(\frac{i \pi}{2}\) radians and the reflections being \(s_i\) where \(i = 1, 2, 3, 4\). Note, in particular, that the lines of reflection 1 and 3 are midpoint to midpoint whilst 2 and 4 are vertex to vertex.

   

   There are three colour choices for each of the four edges. This gives \[|X| = 3^4 = 81 = |\, \text{fix}(e) \, |.\] For the rotations (noting that 1 and 3 are relatively prime to 4) we have \[|\, \text{fix}(r_1) \, | = |\, \text{fix}(r_3) \, | = 3. \] and \[|\, \text{fix}(r_2) \, | = 3^2 = 9. \] For the reflections (using the principles established in Q1) we have\[|\, \text{fix}(s_1) \, | = |\, \text{fix}(s_3) \, | = 3^3 = 27. \] and \[|\, \text{fix}(s_2) \, | = |\, \text{fix}(s_4) \, | = 3^2 = 9. \] Then, by Burnside’s Lemma, the number of orbits (and, hence, the number of distinct colourings) is \[\frac{1}{|G|} \sum \, |\, \text{fix}(g) \, | = \frac{1}{8} \, ( 81 + (2 \times 3) + 9 + (2 \times 3^2) + (2 \times 3^3)) = 21.\]

2. The pentagon: The case for a regular pentagon is straightforward. \[|\, \text{fix}(e) \, | = 3^5 = 243.\] Since the number of sides is prime, the size of the fix for all rotations is the same (since for each \(r_i\) we have that \(i\) is relatively prime to 5). Hence \[|\, \text{fix}(r_i) \, | = 3 \quad \forall i, \; i = 1, 2, 3, 4. \] Furthermore, as there is only one type of reflection (each one passes from a vertex to the midpoint of the opposite side) we have

   

   \[|\, \text{fix}(s_i) \, | = 3^3 = 27 \quad \forall i, \; i = 1, 2, 3, 4, 5.\] Then, by Burnside’s Lemma, the number of orbits (and, hence, the number of distinct colourings) is \[\frac{1}{|G|} \sum \, |\, \text{fix}(g) \, | = \frac{1}{10} \, ( 243 + (4 \times 3) + (5 \times 27)) = 39.\]

Question 3.4

Use Burnside’s Lemma to count the distinguishable colourings of the edges of a square with four distinct colours when two colourings are indistinguishable if one can be obtained from the other by

1. a rotation of the square,
2. a rotation or reflection of the square.

Solution 3.4

We use the same reasoning as in the previous examples.

1. Rotation of the square: There are four colour choices for each of the four edges. This gives \[|X| = 4^4 = 256 = |\, \text{fix}(e) \, |.\] For the rotations (noting that 1 and 3 are relatively prime to 4) we have \[|\, \text{fix}(r_1) \, | = |\, \text{fix}(r_3) \, | = 4. \] (all edges have the same colour), and \[|\, \text{fix}(r_2) \, | = 4^2 = 16. \] (opposite edges have the same colour). Then, by Burnside’s Lemma, the number of distinct colourings is \[\frac{1}{|G|} \sum \, |\, \text{fix}(g) \, | = \frac{1}{4} \, ( 256 + 16 + (2 \times 4)) = 70.\]
2. Rotation or reflection of the square: We need, in addition to the above, to consider the reflections in addition to the rotations. So, the whole of \(D_4\) is acting. For the reflections we have: \[|\, \text{fix}(s_1) \, | = |\, \text{fix}(s_3) \, | = 4^3 = 64. \] and \[|\, \text{fix}(s_2) \, | = |\, \text{fix}(s_4) \, | = 4^2 = 16. \]
   Then, by Burnside’s Lemma, the number of orbits (and, hence, the number of distinct colourings) is \[\frac{1}{|G|} \sum \, |\, \text{fix}(g) \, | = \frac{1}{8} \, ( 256 + 16 + (2 \times 4) + (2 \times 4^2) + (2 \times 4^3)) = 55.\]

Question 3.5

Use Burnside’s Lemma to enumerate the distinguishable colourings of the regions of the following square grid using at most two colours:

1. under the group of rotations of the square;
2. under the full dihedral group \(D_4\).

Give an example of two colourings that are distinguishable in part a. but not in part b.

Solution 3.5

1. rotations of the square: The number of distinguishable colourings is given by the number of orbits of the action of the rotation group, \(\{e, r_1, r_2, r_3 \}\), on the set of all colourings of the figure. We use the usual notation. There are just two colour choices for each of the nine regions. This gives \[|X| = 2^9 = 512 = |\, \text{fix}(e) \, |.\] For the rotations \(r_1\) and \(r_3\) (noting that 1 and 3 are relatively prime to 4) we must have that each of the corner squares must be the same colour as each other and each of the mid-side squares must be the same colour as each other (though not necessarily different from the corner squares), with the centre square being any of the two colours we choose. Thus: \[|\, \text{fix}(r_1) \, | = |\, \text{fix}(r_3) \, | = 2^3 = 8. \]

   

   and for the rotation \(r_2\) (through \(\pi\) radians) we have the following: \[|\, \text{fix}(r_2) \, | = 2^5 = 32. \]

   

   Then, by Burnside’s Lemma, the number of distinct colourings is \[\frac{1}{|G|} \sum \, |\, \text{fix}(g) \, | = \frac{1}{4} \, ( 512 + 2^5 + (2 \times 8)) = 140.\]

2. under the full dihedral group \(D_4\)

   For the reflections we note that there are two types of line of symmetry; vertex to vertex and mid-point to mid-point. For mid-point to mid-point we have:

   

   \[|\, \text{fix}(s_1) \, | = |\, \text{fix}(s_3) \, | = 2^6 = 64. \] For vertex to vertex we have:

   

   \[|\, \text{fix}(s_2) \, | = |\, \text{fix}(s_4) \, | = 2^6 = 64. \] Then, by Burnside’s Lemma, the number of distinct colourings is (taking into account rotations and reflections) \[\frac{1}{|G|} \sum \, |\, \text{fix}(g) \, | = \frac{1}{8} \, ( 512 + 2^5 + (2 \times 8) + (4 \times 2^6)) = 102.\]

Note that for all rotations, colourings will be distinguishable if any given pair of diametrically opposed squares are not of the same colour. All we then need to do is to construct a colouring with that property but which has reflective symmetry about a line of symmetry. Given what we have said about diagonally opposed pairs, it makes sense to use a line of symmetry that is mid-point to mid-point, and we shall use the vertical line. So, in the diagram below, no rotation will turn the configuration on the left to the one on the right, but the right configuration is a reflection of the left configuration.

Question 3.6

A teacher has a bank of \(n\) test questions and wants to assign to each of 3 students, \(A\), \(B\), \(C\), one of the \(n\) questions in this bank. The teacher is not concerned if the same question is assigned to more than one student, and is not concerned about the order in which the questions are assigned to the students. Using Burnside’s Lemma determine the number of essentially different ways of assigning a question from the bank to each student.

Solution 3.7

Let \(X\) be the set of all valid assignment of test questions to the students. The size of \(X\) is \(n^3\) (since the same question can be assigned to more than \(1\) student).

Let \(T_1, T_2, T_3\) be test questions, write \(T_1T_2T_3\) for the assignment \(T_1 \to A\), \(T_2 \to B\) and \(T_3 \to C\). Since the teacher is not concerned about the order in which questions are allocated to students, we consider two assignments equal if they use the same test questions. In particular if \(T_1, T_2\) and \(T_3\) are test questions, then the assigment \(T_1T_2T_3\) is equivalent to any assigment in the set
\[\{T_1T_2T_3,T_1T_3T_2, T_2T_1T_3, T_2T_3T_1, T_3T_1T_2, T_3T_2T_1\}.\] In particular, two assignments \(T_1T_2T_3\) and \(t_1t_2t_3\) are equal if there is an element \(\sigma \in S_3\) such that \(t_1t_2t_3 = T_{\sigma(1)}T_{\sigma(2)}T_{\sigma(3)}\).

Now that we know what the acting group is, we can apply Burnside’s Lemma.

The identity permutation fixes all assignments: \(|\fix(())|| = n^3\).

An assigment is fixed by a three cycle, if and only if it is of the form \(TTT\) for \(T\) a test question. Therefore for \(\sigma\) a three cycle, \(|\fix(\sigma)| = n\).

The 2-cycle \((1 \ 2)\) fixes all assigments of the form \(TTT'\) for \(T\) and \(T'\) test questions. Thus \(|\fix((1\ 2))| = n^2\). A similar argument holds for the other 2-cycles. In particular, for \(\sigma\) a 2-cycle, \(|\fix(\sigma)| = n^2\).

By Burnside’s Lemma, the number of essentiall different assigments, is:

\[ \frac{n^3 + 2n + 3n^2}{6}.\]

Question 3.7

Consider the proof of Cauchy’s Theorem with \(G = D_5\) and \(p = 5\). Describe the set \(X\) and the group acting on \(X\). Determine the possible sizes of the orbits in \(X\) under this action and write out, in full, two distinct orbits for each of these possible sizes.

Solution 3.7

\(X = \{(g_1, g_2, g_3, g_4, g_5) \in G^5 \; | \; g_1g_2g_3g_4g_5 = e \}\) so \(|X| = 10^4 = 2^4 \times 5^4\), which is a multiple of 5. The group acting on \(X\) is \(\langle (1 \; 2 \; 3 \; 4 \; 5) \rangle\) which is the cyclic group of order 5 and since the size of each orbit divides 5 this must have size either 1 or 5. Orbits of size 1 correspond to the identity or elements of order 5, so two such orbits are \[\{(e, e, e, e, e)\} \quad \text{and} \quad \{(r_1, r_1, r_1, r_1, r_1) \}.\] Orbits of size 5 can take a variety of forms, but two simple examples (which are independent of how we define \(D_5\)) are \[\begin{align*} \{&(e, r_1, r_2, r_3, r_4), (r_1, r_2, r_3, r_4, e), (r_2, r_3, r_4, e, r_1),\\ &(r_3, r_4, e, r_1, r_2), (r_4, e, r_1, r_2, r_3)\} \end{align*}\] and \[\begin{align*} \{&(s_1, s_1, s_2, s_2, e), (s_1, s_2, s_2, e, s_1), (s_2, s_2, e, s_1, s_1),\\ &(s_2, e, s_1, s_1, s_2), (e, s_1, s_1, s_2, s_2)\}. \end{align*}\]